package leetcode_BFS;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 01 矩阵
 * <p>算法: 多源 BFS</p>
 * @author yezh
 * @date 2023/8/14 16:33
 */
public class _542 {

    public static int[][] updateMatrix(int[][] mat) {
        // 记录 0 的位置, 取最小距离
        int m = mat.length, n = mat[0].length;
        Deque<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) queue.offer(new int[]{i, j});
                else mat[i][j] = -1;
            }
        while (!queue.isEmpty()) {
            int len = queue.size();
            while (len-- > 0) {
                int[] poll = queue.poll();
                int r = poll[0], c = poll[1], dis = mat[r][c] + 1;
                // 当前格子第一次被遍历到, 就是最近的距离, 因为 BFS 可以算出最短路径
                if (r + 1 < m && mat[r + 1][c] == -1) {
                    mat[r + 1][c] = dis;
                    queue.offer(new int[]{r + 1, c});
                }
                if (r - 1 >= 0 && mat[r - 1][c] == -1) {
                    mat[r - 1][c] = dis;
                    queue.offer(new int[]{r - 1, c});
                }
                if (c + 1 < n && mat[r][c + 1] == -1) {
                    mat[r][c + 1] = dis;
                    queue.offer(new int[]{r, c + 1});
                }
                if (c - 1 >= 0 && mat[r][c - 1] == -1) {
                    mat[r][c - 1] = dis;
                    queue.offer(new int[]{r, c - 1});
                }
            }
        }
        return mat;
    }

}
